反转单链表和双链表。
解答1[Java]:
核心思想
设计两个指针,一个 prev指向前一个节点 ,一个cur 指向当前节点。最初的时候,prev指向null,cur指向第一个节点。最后 cur 指向 null 的时候,prev 刚好指向最后一个节点。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
解答2[Java]:
核心思想
主要是利用 head.next.next = head;
相当于把当前节点的下一个节点指向了当前节点。递归调用到最后,p 一直是指向最后一个节点,并且不断被返回到上一层调用的。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}
拓展:反转双向链表
核心思路
代码
双向链表节点定义
public class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
this.value = data;
}
}
算法
class Solution {
public static DoubleNode reverseList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode post = null;
while (head != null) {
post = head.next;
head.next = pre;
head.last = post;
pre = head;
head = post;
}
return pre;
}
}
完整测试代码
public class Code_07_ReverseList {
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node reverseList(Node head) {
Node pre = null;
Node post = null;
while (head != null) {
post = head.next;
head.next = pre;
pre = head;
head = post;
}
return pre;
}
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
this.value = data;
}
}
public static DoubleNode reverseList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode post = null;
while (head != null) {
post = head.next;
head.next = pre;
head.last = post;
pre = head;
head = post;
}
return pre;
}
public static void printLinkedList(Node head) {
System.out.print("Linked List: ");
while (head != null) {
System.out.print(head.value + " ");
head = head.next;
}
System.out.println();
}
public static void printDoubleLinkedList(DoubleNode head) {
System.out.print("Double Linked List: ");
DoubleNode end = null;
while (head != null) {
System.out.print(head.value + " ");
end = head;
head = head.next;
}
System.out.print("| ");
while (end != null) {
System.out.print(end.value + " ");
end = end.last;
}
System.out.println();
}
public static void main(String[] args) {
Node head1 = new Node(1);
head1.next = new Node(2);
head1.next.next = new Node(3);
printLinkedList(head1);
head1 = reverseList(head1);
printLinkedList(head1);
DoubleNode head2 = new DoubleNode(1);
head2.next = new DoubleNode(2);
head2.next.last = head2;
head2.next.next = new DoubleNode(3);
head2.next.next.last = head2.next;
head2.next.next.next = new DoubleNode(4);
head2.next.next.next.last = head2.next.next;
printDoubleLinkedList(head2);
printDoubleLinkedList(reverseList(head2));
}
}